Lompat ke isi

Subgraf terinduksi

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas


Dalam teori graf, suatu subgraf terinduksi (bahasa Inggris: induced subgraph) dari suatu graf merupakan graf lain yang terbentuk dari subhimpunan dari simpul graf, dan semua sisi (yang ada di graf aslinya) menghubungkan pasangan simpul di subhimpunan tersebut.

Secara formal, misalkan adalah sebarang graf, dan misalkan adalah sebarang subhimpunan dari simpul G. Maka subgraf terinduksi merupakan graf yang himpunan simpulnya adalah serta himpunan sisinya terdiri dari semua sisi di yang memiliki dua buah simpul ujung di .[1] Dalam artian, untuk sebarang dua simpul , dan dikatakan bertetanggaan di jika dan hanya jika kedua buah simpul tersebut bertetanggaan di . Definisi yang sama ini berlaku pula untuk graf tak berarah, graf berarah, dan bahkan multigraf.

Masalah ular di sebuah kotak melibatkan lintasan terinduksi terpanjang di graf hiperkubus.

Di bawah berikut merupakan jenis-jenis subgraf terinduksi yang penting:

Komputasi

[sunting | sunting sumber]

Masalah isomorfisme subgraf terinduksi merupakan sebuah masalah yang terbentuk dari masalah isomorfisme subgraf. Masalah tersebut bertujuan untuk menguji apakah suatu graf dapat ditemukan sebagai suatu subgraf terinduksi dari yang lain. Masalah ini merupakan masalah NP karena meliputi masalah clique sebagai kasus istimewa.[4]

  1. ^ Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, hlm. 3–4, ISBN 9783540261834 
  2. ^ Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 
  3. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070alt=Dapat diakses gratis, doi:10.4007/annals.2006.164.51, MR 2233847 
  4. ^ Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733